package com.sourcetrip.raw.adt;

import com.sourcetrip.raw.adt.abs.MyAbstractLinkedList;

/**
 * @author: ZhouBert
 * @date: 2020/11/17
 * @description: 实现集合功能的【动态数组集合】 发现 AbstractList<E> 这个抽象类居然只有两个抽象方法！
 * --
 * 还是决定实现一遍 动态数组集合
 * 除了正常的功能以外，还具有 缩容的功能
 * --
 * 分析:
 * size - 实际的大小;elements.length - 数组（容器的长度）;index
 * 这三个的关系跟链表里是不一样的
 */
public class MyArrayList<E> extends MyAbstractLinkedList<E> {

	private int DEFAULT_CAPACITY = 10;

	private Object[] elements = null;

	//region	constructor

	public MyArrayList() {
		elements = new Object[DEFAULT_CAPACITY];
		size = 0;
	}

	public MyArrayList(int capacity) {
		elements = new Object[capacity];
		size = 0;
	}

	//endregion


	/**
	 * 执行添加
	 *
	 * @param index
	 * @param element
	 */
	@Override
	public void add(int index, E element) {
		checkIndex4add(index);

		//如果添加之前，容器大小 == 实际大小
		if (size == elements.length) {
			//执行扩容
			grow();
		}
		//将元素添加到指定的位置
		//1.将 index 开始的元素往后移动
		for (int i = size; i > index; i--) {
			elements[i] = elements[i - 1];
		}
		//2.赋值
		elements[index] = element;
		size++;
	}


	@Override
	public E get(int index) {
		checkIndex4get(index);
		return (E) elements[index];
	}

	@Override
	public E set(int index, E element) {
		checkIndex4get(index);
		E oldValue = (E) elements[index];
		elements[index] = element;
		return oldValue;
	}

	/**
	 * 具有【缩容】能力的 remove
	 *
	 * @param index
	 * @return
	 */
	@Override
	public E remove(int index) {
		checkIndex4get(index);
		E oldValue = (E) elements[index];
		//将index 之后的位置前移
		for (int i = index; i < size; i++) {
			elements[i] = elements[i + 1];
		}
		size--;
		//当 size < (elements.length>>1) 时进行缩容
		if (size < (elements.length >> 1)) {
			trim();
		}
		return oldValue;
	}

	@Override
	public int indexOf(E element) {
		//遍历
		//区分 null
		if (element == null) {
			for (int i = 0; i < size; i++) {
				if (elements[i] == null) {
					return i;
				}
			}
		} else {
			for (int i = 0; i < size; i++) {
				if (element.equals(elements[i])) {
					return i;
				}
			}
		}
		return ELEMENT_NOT_FOUND;
	}

	@Override
	public void clear() {
		//根据 可达性算法，外界并不知道数组，也就是GC ROOT 到达不了 elements
		size = 0;
	}

	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();
		sb.append("[");
		for (int i = 0; i < size; i++) {
			if (i == 0) {
				sb.append(elements[i]);
			} else {
				sb.append(", ").append(elements[i]);
			}
		}
		sb.append("]");
		return sb.toString();
	}


	//region	private methods

	/**
	 * 进行扩容
	 */
	private void grow() {
		//扩容 1.5 倍
		int nsize = elements.length + (elements.length >> 1);
		Object[] newElements = new Object[nsize];
		//进行数组的拷贝
		System.arraycopy(elements, 0, newElements, 0, elements.length);
		elements = newElements;
	}

	/**
	 * 进行缩容
	 */
	private void trim() {
		//新的 nsize 取决于 DEFAULT_CAPACITY 和 size+1 的最大值
		int nsize = Math.max(size + 1, DEFAULT_CAPACITY);
		Object[] newElements = new Object[nsize];
		//进行数组的拷贝
		System.arraycopy(elements, 0, newElements, 0, size);
		elements = newElements;
		System.out.println("进行了缩容：size:" + size + ";length:" + elements.length);
	}

	//endregion
}
